The Internet or world wide web can be viewed as a “directed graph,” in which web pages are the nodes of the graph, and each directed edge of the graph indicates a hyperlink from one web page to another. The norm of a node or web page is thus the number of outward-pointing links from this node, denoted |P|. The rank of a node is given by the equation:r(Pi)=Σjeln(i)r(Pj)/|P|. 
PageRank values for web pages play an important role in the method used to determine the order of search results displayed to a user who initiates a search on key words or phrases. Search engines thus use PageRank values and other parameters to determine the ordering of the web pages produced in response to search queries of the Internet, subsets of the Internet, or other networks. The ranks r(P) of nodes or web pages are conventionally computed through an iterative process using over one hundred heuristics to guarantee convergence. The iterative system is given by:rk+1=rkGin which G is a large sparse matrix. Each entry in the jth row of G is either 0 or 1/|Pj|.
As the size of the Internet has continued to grow over time, the number of nodes in the graph has increased by more than two orders of magnitude. More specifically, the number of web pages on the world wide web has recently grown from about 109 to 1010 and will soon be more than 1011. The iterative solvers that are now used to determine PageRank operate in O(N2) time in the number of nodes, so using the current methods to compute PageRank for 1011 web pages in the future will require about 100 to 10,000 times as long to compute as is currently the case.
In addition, the connectivity of web pages on the Internet is increasing, which means that the matrix G is becoming less sparse and will have increasingly more dense sub-matrices corresponding to online communities, blogs, and social networks, each of which represents a block of related interconnected nodes. Sparse matrix techniques operate in O(N2) time in the number of nodes and require O(N2) memory. With the growth in the size of the Internet, this increased time and degradation of memory performance will become a problem, unless alternative approaches are used to determine PageRank and related web page scores.
Other requirements that are being considered will also increasingly impact on the need for efficiently determining the ranking of web pages. For example, it has been recommended that search and ranking be user-dependent. The effect of making such a change in the current manner of determining rankings for web pages would be to replace the uniform row-weights in the G matrix with other values. All of these trends will combine to create a new matrix H, which is large and dense. Accordingly, a new approach will be needed to derive rankings from H, with efficiency in both time and memory requirements.